#leetcode题目74：搜索二维矩阵
#难度：中等
#时间复杂度：O(logmn)
#空间复杂度：O(1)
#方法：二分查找


from typing import List
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # 第一次二分查找：找到目标行
        left = 0
        right = len(matrix) - 1
        target_row = -1
        
        while left <= right:
            mid = left + ((right - left) >> 1)  # 防止溢出
            
            if matrix[mid][0] == target:
                # 如果第一列元素等于目标值，直接返回True
                target_row = mid
                left = mid + 1  # 继续寻找可能的更大行索引
            elif matrix[mid][0] > target:
                # 如果第一列元素大于目标值，目标可能在更小的行
                right = mid - 1
            else:
                # 如果第一列元素小于目标值，目标可能在这一行或更大的行
                target_row = mid
                left = mid + 1
        
        # 如果没有找到合适的行，返回False
        if target_row < 0:
            return False
        
        # 第二次二分查找：在目标行中查找目标值
        row = matrix[target_row]
        left = 0
        right = len(row) - 1
        
        while left <= right:
            mid = left + ((right - left) >> 1)
            
            if row[mid] == target:
                return True
            elif row[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        
        return False




#测试数据
matrix=[[1,3,5,7],[10,11,16,20],[23,30,34,60]]
target=3
#预期输出：True
solution=Solution()
print(solution.searchMatrix(matrix,target))

matrix=[[1,3,5,7],[10,11,16,20],[23,30,34,60]]
target=13
#预期输出：False
solution=Solution()
print(solution.searchMatrix(matrix,target))


       